# -*- coding: utf-8 -*- 
# @project : 《剑指offer》
# @Author : created by bensonrachel on 2021/6/12
# @File : 快速幂.py
# 《数值的整数次方》 2021-12-27字节数据挖掘面试考过，还考了水塘抽样的函数怎么实现
# 水塘抽样 ： 抽一个还是抽k个的：https://labuladong.gitee.io/algo/4/30/119/
class Solution(object):
    def Power(self, base, exponent):#二进制法最容易理解这个快速幂，目的是怎么快速且不溢出地求一个很大的幂。
        """
        :type base: float
        :type exponent: int
        :rtype: float
        """
        if (exponent == 0):
            return 1
        if (exponent > 0):
            a = 1
            while (exponent):
                if (exponent % 2 == 1): a = a * base#指数的二进制的最后一位是1的就是要乘这一个数，根据二进制去思考，如果是0就不要这一次翻倍的这个数
                base = base * base#每次翻倍，x x平方 x四次方这样
                exponent = exponent // 2
            return a
        if (exponent < 0):
            exponent = - exponent
            a = 1
            while (exponent):
                if (exponent % 2 == 1): a = a * base
                base = base * base
                exponent = exponent // 2
            return 1 / a
